/**
 * 题目描述：
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */

/**
 * 构建思路：
 * 1. 前序遍历找到根结点root
 * 2. 找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
 * 3. 截取左子树的中序遍历、右子树的中序遍历
 * 4. 截取左子树的前序遍历、右子树的前序遍历
 * 5. 递归重建二叉树
 */


import { Node, Tree } from './构建二叉树.js'

function reConstructBinaryTree(pre, vin) {
    if (pre.length === 0) {
        return null;
    }
    if (pre.length === 1) {
        return new Node(pre[0])
    }
    const root = pre[0]; // 1. 取前序遍历的根结点
    const rootIndex = vin.indexOf(root); // 2. 找到根结点在中序遍历的位置
    const vinLeft = vin.slice(0, rootIndex); // 3.1 获取中序遍历左子树的长度
    const vinRight = vin.slice(rootIndex + 1); // 3.2 获取中序遍历右子树的长度
    const preLeft = pre.slice(1, rootIndex + 1); // 4.1 获取前序遍历左子树的长度
    const preRight = pre.slice(rootIndex + 1); // 4.2 获取前序遍历右子树的长度
    const node = new Node(root)
    node.left = reConstructBinaryTree(preLeft, vinLeft); // 5. 递归构建
    node.right = reConstructBinaryTree(preRight, vinRight);
    return node;
}


/**
 * 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历
 * 思路与重建二叉树类似
 */
function getHRD(pre, vin) {
    if (!pre) {
        return [];
    }
    if (pre.length === 1) {
        return pre;
    }
    const root = pre[0];
    const rootIndex = vin.indexOf(root);
    const vinLeft = vin.substring(0, rootIndex);
    const vinRight = vin.substring(rootIndex + 1);
    const preLeft = pre.substring(1, rootIndex + 1);
    const preRight = pre.substring(rootIndex + 1);
    return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + root;
}

const pret = [1, 2, 4, 7, 3, 5, 6, 8];
const int = [4, 7, 2, 1, 5, 3, 8, 6];
const bt = reConstructBinaryTree(pret, int)
console.log(bt)

const a = 'FDXEAG'
const b = 'XDEFAG'
const post = getHRD(a, b)
console.log(post)